#define _CRT_SECURE_NO_WARNINGS 1
bool cmp(ListNode* A, ListNode* B) {
    return A->val < B->val;
}
class Solution {
public:

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int k = lists.size();
        if (k == 0)return nullptr;
        vector<ListNode*> res;
        for (int i = 0; i < k; i++) {
            ListNode* cur = lists[i];
            while (cur) {
                res.push_back(cur);
                cur = cur->next;
            }
        }
        if (res.size() == 0)return nullptr;
        sort(res.begin(), res.end(), cmp);

        ListNode* ans = res[0];
        for (int i = 1; i < res.size(); i++) {
            res[i - 1]->next = res[i];
        }
        res[res.size() - 1]->next = nullptr;
        return res[0];
    }
};